package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode17 电话号码的字母组合
 * @date 2024/12/5 11:45
 */
public class E17 {

    /**
     * <h3>方法一，用剪枝的思想</h3>
     *
     * @param digits digits
     * @return 所有组合
     */
    public List<String> letterCombinations1(String digits) {
        List<String> result = new ArrayList<>();
        if (digits.isEmpty()) {
            return result;
        }
        char[] digitsArray = digits.toCharArray();
        dfs(result, digitsArray, new StringBuilder(), 0);
        return result;
    }

    /**
     * 回溯
     *
     * @param result      结果集
     * @param digits      数字
     * @param currCombine 当前组合
     * @param depth       深度
     */
    private void dfs(List<String> result, char[] digits, StringBuilder currCombine, int depth) {
        if (digits.length == depth) {
            result.add(currCombine.toString());
            return;
        }
        // 计算当前数字对应的字母的起始索引
        int begin;
        if (digits[depth] <= '7') {
            begin = (digits[depth] - '2') * 3;
        } else if (digits[depth] == '8') {
            begin = 19;
        } else {
            begin = 22;
        }
        for (int i = 0; i < 4; i++) {
            // 剪枝，跳过不足四个的
            if (i == 3 && begin != 22 && begin != 15) {
                continue;
            }
            int currIndex = begin + i;
            char curr = (char) (currIndex + 'a');
            currCombine.append(curr);
            dfs(result, digits, currCombine, depth + 1);
            currCombine.setLength(currCombine.length() - 1);
        }
    }

    /**
     * <h3>方法二：结合哈希表和事先确定count</h3>
     *
     * @param digits 数字
     * @return 所有组合
     */
    public List<String> letterCombinations2(String digits) {
        List<String> result = new ArrayList<>();
        if (digits.isEmpty()) return result;
        char[] digitsArray = digits.toCharArray();
        HashMap<Integer, Integer> map = new HashMap<>();
        fill(map);
        dfs(result, digitsArray, new StringBuilder(), 0, map);
        return result;
    }

    /**
     * 填充哈希表
     *
     * @param map 哈希表
     */
    private void fill(HashMap<Integer, Integer> map) {
        map.put(2, 0);
        map.put(3, 3);
        map.put(4, 6);
        map.put(5, 9);
        map.put(6, 12);
        map.put(7, 15);
        map.put(8, 19);
        map.put(9, 22);
    }

    /**
     * 回溯
     *
     * @param result      结果集
     * @param digits      数字
     * @param currCombine 当前组合
     * @param depth       深度
     * @param map         哈希表
     */
    private void dfs(List<String> result, char[] digits, StringBuilder currCombine, int depth, HashMap<Integer, Integer> map) {
        if (digits.length == depth) {
            result.add(currCombine.toString());
            return;
        }
        int begin = map.get(digits[depth] - '0');
        int count = begin == 22 || begin == 15 ? 4 : 3;
        for (int i = 0; i < count; i++) {
            int currIndex = begin + i;
            char curr = (char) (currIndex + 'a');
            currCombine.append(curr);
            dfs(result, digits, currCombine, depth + 1, map);
            currCombine.setLength(currCombine.length() - 1);
        }
    }

    /**
     * <h3>方法三：结合哈希表直接存放所有，思路清晰但是空间复杂度相对较高</h3>
     *
     * @param digits 数字
     * @return 所有组合
     */
    public List<String> letterCombinations3(String digits) {
        List<String> result = new ArrayList<>();
        char[] charArray = digits.toCharArray();
        if (charArray.length == 0) return result;
        HashMap<Integer, char[]> map = new HashMap<>();
        fill2(map);
        dfs(charArray, result, map, new StringBuilder(), 0);
        return result;
    }

    /**
     * 填充哈希表
     *
     * @param map 哈希表
     */
    private void fill2(HashMap<Integer, char[]> map) {
        map.put(2, new char[]{'a', 'b', 'c'});
        map.put(3, new char[]{'d', 'e', 'f'});
        map.put(4, new char[]{'g', 'h', 'i'});
        map.put(5, new char[]{'j', 'k', 'l'});
        map.put(6, new char[]{'m', 'n', 'o'});
        map.put(7, new char[]{'p', 'q', 'r', 's'});
        map.put(8, new char[]{'t', 'u', 'v'});
        map.put(9, new char[]{'w', 'x', 'y', 'z'});
    }

    /**
     * 回溯
     *
     * @param charArray   数字
     * @param result      结果集
     * @param map         哈希表
     * @param currCombine 当前组合
     * @param index       当前下标
     */
    private void dfs(char[] charArray,
                     List<String> result,
                     HashMap<Integer, char[]> map,
                     StringBuilder currCombine,
                     int index) {
        if (index == charArray.length) {
            result.add(currCombine.toString());
            return;
        }
        char[] letters = map.get(charArray[index] - '0');
        for (char letter : letters) {
            currCombine.append(letter);
            dfs(charArray, result, map, currCombine, index + 1);
            currCombine.setLength(currCombine.length() - 1);
        }
    }
}
